Conference [B]

Memory limit: 32 MB

In Bytetown preparations for the annual Great Bitonic Conference are taking place. There are going to be presentations which - according to the tradition - must take place at exactly the same time. All presentations are organized in identical rooms. Each room can hold up to persons. There are enough rooms to hold all participants of the conference. If there are more than attendance of a presentation, organizers have to book more than one room for it (to be exact, for participants there are ¹ rooms required).

Organizers of the conference would like to maximize their income - the amount of money obtained from selling tickets, decreased by the cost of renting rooms should be as great as possible. The cost of renting one room for people is equal to . A single ticket for the -th presentation costs . The prices of tickets were selected in such way that it is profitable to rent a room for people (it is also possible - however not required - that it is profitable to rent a room for a smaller number of people), meaning that in this case the profit is non-negative. Organizers may cancel some reservations, so that their income is maximized. You implemented the original version of registration system, so it is your job to perform the cancellation process.

Task

Write a program which:

• reads from the standard input the prices of tickets, the size of a room, the cost of renting a room and the list of reservations,
• calculates maximal profit from the conference, that can be obtained by potentially cancelling some of the reserved tickets,
• writes the result to the standard output.

Input

In the first line of the standard input there are four integers: , , and (, , , ), separated by single spaces. They represent: the number of presentations, the number of reservations, the size of a single room and the cost of renting a single room. The second line contains exactly numbers (), separated by single spaces (the lower limit on the value of is due to profitability of renting a room for participants of a conference). They represent prices of tickets for the presentations (numbered from to ). Following lines contain descriptions of reservations. Each reservation is represented by two integers and (, ), separated by a single space. They represent the number of a presentation and the number of tickets booked for this presentation. It is allowed to cancel any number of tickets within the same reservation, not only the whole reservation.

Output

The first and only line of standard output should contain exactly one integer - the total income that can be obtained.

Example

For the input data:

3 2 10 30
7 10 8
1 9
3 13

the correct result is:

83

For the example above, in order to maximize income, 3 tickets from the second reservation should be cancelled.

Task author: Piotr Stanczyk.